In recent years, there has been a dramatic increase in the need for systems that can protect digital data from potential eavesdroppers, forgers, and other adversaries. This is largely due to the fact that an unprecedented portion of all commercial transactions and communications are now handled with digital electronics. In addition, the sophistication of potential adversaries has increased, which has made the problem of protecting digital data even more pressing.
In response to this need, a wide variety of interesting and novel schemes have been developed for protecting and authenticating digital data. The problem now faced by many corporations and government bodies is to choose a scheme from among the many that will be both secure and economical. NIST, in particular, is faced with the task of selecting "standard" methods for encrypting and authenticating data.
Traditionally, written data has been authenticated by appending the handwritten signature of the appropriate individual to the data. Modern methods for authenticating digital data proceed in a similar fashion except that the handwritten signature is replaced with a digital signature. The digital signature consists of a stream of bits which is computed by the signer based on the message being signed. The digital signature should have the properties that anyone can verify that a signature is the valid signature of the signer for the associated message, and that only the signer is able to generate the signature.
An exemplary method for computing digital signatures today is the RSA scheme. In the RSA scheme, each individual is provided with a secret pair of large (e.g., 500-digit) prime numbers P.sub.1 and P.sub.2. The pair (P.sub.1,P.sub.2) is referred to as the secret key for the individual. The corresponding public key for the individual is the pair (Q,r) where Q=P.sub.1 P.sub.2 and r is a fixed positive integer that is relatively prime to P.sub.1 -1 and P.sub.2 -1. The signature for a message M is a number x for which x.sup.r =h(M)mod Q. The function h is a publicly-available hash function that maps any data string M into a k-bit number where generally k.ltoreq.log Q. The step of computing h(M) is known as pre-hashing. This initial step is common to all known digital signature algorithms because applying the signing procedure directly to M, rather than h(M), may be either impossible or impossibly time-consuming. The hash function h used for pre-hashing needs to be secure, i.e., easy to compute and behaving in practice like a random function (such a secure function H has two important properties: it is easy to compute h(M) given M but impossibly hard to compute M given h(M), i.e., h is "one-way", and it is impossibly hard to find two strings M and M' such that h(M)=h(M')).
Many similar schemes have also been proposed, including the well-known DSA algorithm. The practicality of schemes such as RSA and DSA is based on several factors: it is not overly difficult for an individual's computer to produce a signature x for a message M given that the computer knows the secret key (P.sub.1, P.sub.2), the fact that it is relatively easy for someone else's computer to verify that x is a signature for M given knowledge of the public key (Q,r), the fact that the signature itself is relatively short (e.g., it consists of about 1000 bits), and the fact that the public key is also relatively short (e.g., it also consists of about 1000 bits).
For a digital signature algorithm to be secure, it must be practically impossible for an adversary to produce a signature for any message M without knowledge of the private key, even if the adversary is aware of the public key and can obtain valid signatures for messages other than M. More specifically, the security of RSA and DSA schemes is based on the hope that number-theoretic problems such as factoring and computing discrete logarithms are impossibly hard for almost all large numbers, the hope that the hash function used for pre-hashing is secure, and, most importantly, the hope that the adversary must be able to factor or solve the discrete log problems in order to be able to forge a signature. In fact, there is no proof that forging RSA signatures is as hard as factoring or that forging DSA signatures is as hard as computing discrete logs even if a secure hash function were used for prehashing.
For example, if the adversary is able to factor, then he can compute the private key from the public key, whereupon he can begin to forge signatures at will for the RSA scheme. If the adversary can compute discrete logarithms, then he can compute forged signatures for the DSA scheme directly, without knowledge of the secret key. Moreover, if the adversary can find two messages M and M' for which h(M)=h(M'), then he can forge a signature for M' by obtaining a legitimate signature for M (since the signatures for M and M' are the same). If the adversary can invert h, then he can forge signatures by an alternative method using a slightly more complex attack. Finally, and most importantly, it might be possible for an adversary to forge signatures using an altogether different as-yet-unknown attack. Hence, in addition to the hope that it is not possible to achieve a known attack, the security of schemes such as RSA depend on the hope that there are no easier alternative attacks. In summary, this means that the security of signature schemes such as RSA and DSA is based on assumptions which may not always be defensible.